/*
 * @lc app=leetcode.cn id=188 lang=golang
 *
 * [188] 买卖股票的最佳时机 IV
 */

// @lc code=start
func maxProfit(k int, prices []int) int {
	if len(prices) == 1 {
		return 0
	}
	dp := make([][]int, len(prices))
	for i := 0; i < len(prices); i++ {
		dp[i] = make([]int, 2*k+1)
	}
	dp[0][0] = 0 // 未持有股票，没有买,
	for j := 1; j <= 2*k; j += 2 {
		dp[0][j] = -prices[0] // 持有股票，  第j次买
		dp[0][j+1] = 0        // 未持有股票，第j次卖

	}
	for i := 1; i < len(prices); i++ {
		dp[i][0] = dp[i-1][0] // 今天结束没买，前一天也没买

		for j := 1; j <= 2*k; j += 2 {
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-prices[i])   // 今天结束第j次买，要么前一天买的，要么今天买的
			dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]+prices[i]) // 今天结束第j次卖，要么前一天卖的，要么今天卖的
		}
	}

	return dp[len(prices)-1][2*k]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

